Zliczanie planów sieci drogowej

Limit pamięci: 64 MB

Bajtazar wybiera się w podróż samochodową po Bajtocji, lecz niestety ma problemy z nabyciem mapy tego kraju. Od znajomych dowiedział się o pewnych właściwościach bajtockiej sieci dróg:

• W Bajtocji jest miast, ponumerowanych od do .
• Każda droga jest dwukierunkowa i łączy ze sobą pewne dwa różne miasta.
• Każde dwa różne miasta są połączone dokładnie jedną trasą, złożoną z jednej bądź większej liczby dróg, na której żadne miasto się nie powtarza.
• Najdłuższa z tras, na której żadne miasto się nie powtarza, składa się z dróg.

Na podstawie zdobytych informacji Bajtazar zamierza spróbować odtworzyć mapę drogową Bajtocji. Żeby się nadmiernie nie napracować, Bajtazar chciałby wiedzieć, ile jest różnych planów sieci drogowej spełniających podane warunki. Przy porównywaniu planów Bajtazar nie bierze pod uwagę dokładnych lokalizacji zaznaczonych miast, a jedynie schemat połączeń; nie interesują go także konkretne numery miast. Innymi słowy, Bajtazar uznaje dwa plany za jednakowe wtedy i tylko wtedy, gdy można miastom z jednego z nich przyporządkować różnowartościowo miasta z drugiego tak, że jeżeli miasta i są połączone drogą na pierwszym planie, to ich odpowiedniki i są także połączone drogą na drugim planie.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczby , oraz ,
• wyznaczy liczbę różnych planów sieci drogowej, zgodnych z informacjami zdobytymi przez Bajtazara, modulo ,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy i jedyny wiersz wejścia zawiera trzy liczby całkowite , oraz (, , , jest liczbą pierwszą), pooddzielane pojedynczymi odstępami.

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą - resztę z dzielenia przez liczby różnych planów, spełniających warunki znane Bajtazarowi.

Przykład

Dla danych wejściowych:

6 3 13

poprawną odpowiedzią jest:

2

Autor zadania: Jakub Radoszewski.